In computing and telecommunications, often a situation is encountered in which from the 2.sup.n possible words with n bits, representing for example instructions, memory locations, node or hosts addresses, only a significantly smaller subset is actually supported or used at a particular place or time. For the purpose of describing the current invention, this smaller number of words is denoted by 2.sup.k, with k being an integer smaller than n. In order to avoid unnecessary expenditures and unused resources, this situation can be solved by a translation of the n-bit words into k-bit words to be used in a local or temporary application. In terms relevant to the related technical field, this translation is known as `lookup` or `mapping` function. A description of the header conversion within a ATM-type switching system, as given below, may serve as an example for this general concept.
The ATM switching technique is currently under development by all major telecommunications equipment manufacturers. ATM is an acronym made up from asynchronous transfer mode. This switching technology allows the exchange of digital data coming from customer premises, e.g. connections from homes or offices, from local area networks (LANs), or from other switches, routers, or gateways. Data transmitted in ATM are divided into standard-size packets, called cells. Each cell has to be provided with a header containing information concerning addressee and receiving node or user. According to currently valid standards, the bit string identifying the receiver of an ATM cell is 28 bits wide and divided into a virtual path identifier field (VPI) and a virtual channel identifier field (VCI). Out of these 2.sup.28 possible addresses, a state-of-the-art ATM switch may support approximately 10,000 at a time, which lets k assume a value of 13 or 14. Thus, the switch allows the conversion of 2.sup.k incoming VPI/VCIs into new VPI/VCIs to enable, for example, the next `hop` of the respective data packets towards their final destination address.
This header conversion is performed by means of a lookup table, in which the incoming VPI/VCI is identified and translated into the VPI/VCI which is paired to it. Comparing the number of supported VPI/VCI values (2.sup.k) with the number of possible VPI/VCIs (2.sup.n, n=28). it is immediately obvious that a simple lookup table which pairs n-bit words is ineffective as the overwhelming number of entries has no counterpart.
This problem is solved by an (intermediate) translation of those n-bit addresses supported by the switch into k-bit words and performing the (final) conversion back to an n-bit word in a second lookup step in a table which has only 2.sup.k entries. As this second lockup step can easily be implemented, the prior art is focused on the problem of mapping or translating the supported n-bit words into k-bit words.
For the n-to-k-bit translation, typically content addressable memories (CAMs) are used. An example for this technique is given in European patent application EP-A-0 500 238, in which the n-bit VPI/VCI is extracted from the header of an incoming ATM cell and fed into a CAM. The k-bit output word of the CAM is used to address a conventional random access memory (RAM), which holds the new VPI/VCI to be attached to the outgoing ATM cell. A similar approach is proposed for a high performance Internet router in IBM's Technical Disclosure Bulletin, Vol.36, No.02, February 1993, pp. 151-153. The Internet protocol (IP) network described therein employs 32-bit addresses for its nodes, but the underlying problem remains the same.
Though being in principle easy to implement, a wide-spread use of CAMs has been prevented by their cost. CAMs have to be specially designed for the simultaneous n-bit wide comparison operation. resulting in a significantly higher number of transistors per bit compared to random access memories. By this reason, several attempts to replace the expensive CAM by less costly RAMs were motivated.
As the present invention can broadly be conceived as a new way of replacing CAMs by RAMs, a short summary of previous proposals for such a replacement will be given in the following.
In the European patent application EP-A-0 459 703, a content addressable memory is described, comprising a RAM array and a counter. Using a decoder, this counter cycles through all entries of the memory array. The outputs of the memory are successively compared to an input signal value. The comparator issues a signal indicating whether or not a match has occurred. When a match is found between the input signal value and the value currently selected from the RAM, the appropriate counter value is applied to a stack buffer. The stack buffer is used to store the value of the counter corresponding to the entry of the RAM for which a match has been found. According to the description, the stack can be organized as a queue, or it may be a single register for storing a single value. No method for translating the input value is described. Further, EP-A-0 459 703 gives no indication concerning a particular arrangement of the entries stored in the RAMA.
A hybrid CAM/RAM circuit is known from EP-A-0 228 917. The signal bus carrying the compared (information to be compared) is split into a first portion, which is applied to a CAM section, and into a second portion which is stored in a comparator. In case of a favorable comparison, the CAM section produces a match signal and a pointer to an entry in the RAM section. This entry is compared to the second portion of the compared (information to be compared) The entries in the RAM section are stored in accordance with the pointers developed by the CAM section. No specific order of entries is mentioned.
A memory structure allowing the maintenance of records in a sorted list according to a search key is described in the international application WO 90/04849 published under PCT. One particular use of the memory structure is as the core of a content addressable memory. Essentially, fast insert and delete operations are described, keeping the defined order of the records in plurality of contiguous memory locations. The sorted list of entrees may be searched by any appropriate search algorithm. As an example for a search algorithm, the binary search is mentioned.
In view of the above mentioned prior art, it is an object of the invention to provide a fast n-bit to k-bit translating or mapping device avoiding the use of any content addressable memories. No constraints should be imposed on the choice of the k-bit words to provide for a wide range of applications. A particular object of the invention is to enable a fast n-bit to k-bit translation for data switches with data throughput above 100 Mbps, especially for an VCI/VPI translation.